1. Field of the Invention
This invention relates to the field of integrated circuit design, and in particular to programmable gate arrays.
2. Description of Related Art
Gate array integrated circuits are common in the art, and allow for the design of application specific integrated circuits via an interconnection among predefined and prefabricated gate array cells. Field Programmable Gate Array (FPGA) allow for the creation, or programming, of the interconnection among the cells at a user""s site, using commonly available programming devices. The interconnections may be created by fusing links, by enabling selected switches, by storing a pattern that controls available switches, and so on. U.S. Pat. No. 5,594,363, xe2x80x9cLogic Cell and Routing Architecture in a Field Programmable Gate Array, filed Jan. 14, 1997 for Freeman et al, incorporated by reference herein, discloses a technique for routing among cells that includes switch matrices that connect select vertical wires to horizontal wires, based on the contents of a nonvolatile memory cell. Typically, a designer provides a description of the function to be performed, and a computer-aided-design (CAD) program determines the interconnect programming required to effect that function. The description may be a logic diagram, a data flow diagram, a state diagram or table, a sequence of instructions in a structured design language, and so on.
The conversion from a description of the design to the programming of a gate array is dependent upon the contents of the gate array. If the cells of the gate array are high level blocks, such as counters, parity generators, and the like, then the amount of programming required is limited to the interconnections among these large, or coarse-grain, cells. If, on the other hand, the cells of the gate array are low level blocks, such as gates, latches, and the like, then the amount of programming is significantly higher, because these smaller, or fine-grain, cells need to be interconnected to effect the higher level functions, such as the aforementioned counters and parity generators. In some designs, higher circuit densities can be achieved via the use of fine-grain cells, because simpler functions can be implemented with a small low-level cell, rather than with a larger high-level cell whose higher level functions go unused. Conversely, some complex designs cannot be efficiently embodied in a fine-grain gate array, because the amount of interconnection required among the low-level cells exceed the capacity of the gate array. In some cases, the interconnections may be within the capacity of the gate array, but the resultant routing paths among the low-level cells exceed the propagation delay or skew limits required to effect the intended function. For optimal performance, the fine-grained cells that are related to a particular function should be co-located, but this often places constraints on the routing for connections among functional blocks when such co-locations create routing xe2x80x9cbottlenecksxe2x80x9d.
Various architectures have been proposed to optimize the tradeoffs among circuit density, routing efficiency, performance limits, and the like. U.S. Pat. No. 5,001,368, xe2x80x9cConfigurable Logic Arrayxe2x80x9d, issued Mar. 19, 1991 to Cliff et al, for example, notes the deficiencies of a gate array architecture that only includes NAND gate cells, and specifies the inclusion of additional circuitry to include a latch function in each cell. The need for a latch function is a common theme in conventional gate array cell design, because if the devices that form the latch are interconnected via long routing paths, or via intermediate buffers, the phase shift that is introduced could cause the latch to oscillate. Typical gate array cells commonly include at least one latch, sometimes more. U.S. Pat. No. 5,055,718, xe2x80x9cLogic Module with Configurable Combinational and Sequential Blocksxe2x80x9d, issued Oct. 8, 1991 to Galbraith et al, specifies a configurable gate array cell that can effect xe2x80x9ca wide varietyxe2x80x9d of combinational and sequential logic functions, ranging from a simple NAND function to an edge-triggered flip-flop with asynchronous reset. As noted above, however, the same amount of cell area is consumed regardless of whether a simple NAND gate or complex flip-flop is being implemented.
To ease the routing task, U.S. Pat. No. 5,831,448, xe2x80x9cFunction Unit for Fine-Grained FPGAxe2x80x9d, issued Nov. 3,1998 to Kean et al, specifies the organization of configurable gate array cells into a hierarchy of blocks, such as a 4xc3x974 cell block, a 4xc3x974 organization of the 4xc3x974 cell block, and so on. Each level of the hierarchy includes a routing path specific to that level, thereby allowing for a routing strategy that is logarithmic in terms of distance. The aforementioned U.S. Pat. No. 5,594,363 also discloses the use of hierarchical routing channels. The Motorola MPA 1000 family of commercially available FPGAs provides multi-functioned configurable gate array cells that are organized in zones of 10xc3x9710 cells and ancillary components, such as port cells and clock distribution cells, the zones being organized into 4 quadrants. A hierarchy of routing paths are provided: a local interconnect provides the connection among adjacent and near-adjacent cells; a medium interconnect provides the interconnection among zones; and a global interconnect provides the interconnection among quadrants, as well as global signal and bus routing.
Although hierarchical routing is effective for managing interconnection complexities, a fixed hierarchy of cells can lead to inefficiencies when the cell hierarchy does not conform to the hierarchy of functions used in the design. Similarly, although multi-functioned configurable cells ease the routing task by containing medium-complexity devices such as flip-flops, the achievable circuit density is directly affected by the number of low-level functions in the design, because regardless of simplicity, they will each consume a medium-complexity, medium-sized cell. Additionally, the partitioning of the area into zones of logic elements and zones of routing paths can also lead to inefficiencies when available logic elements are made unaccessible due to a commitment of all available routing paths to other logic elements, or preferred routing paths are made unaccessible to particular logic elements.
It is an object of this invention to provide a gate array architecture having a very fine grain cell configuration. It is a further object of this invention to provide a gate array architecture that facilitates efficient routing among cells. It is a further object of this invention to provide a gate array architecture that supports a user definable hierarchy of gate array cells. It is a further object of this invention to provide a gate array cell that facilitates the creation of user definable macro cells.
These objects and others are achieved by providing a very fine-grained gate array cell, and by providing a cell layout that facilitates a xe2x80x9csea of cellsxe2x80x9d allocation and routing technique. A preferred gate array cell includes a well defined xe2x80x9ccorexe2x80x9d element whose replication allows for embodiments of logic with minimal unused potential. In a preferred embodiment, the gate array cell comprises a two-input logic device and a cascade NAND gate with buffer. The NAND gate accepts a cascade input from another cell, and the cascade output of the NAND gate is provided as a cascade input to the other cell to facilitate the efficient implementation of cross-coupled devices. In another preferred embodiment, the gate array cell comprises a three-input neural cell. To ease the routing task, in these preferred embodiments, the output of each gate array cell is pre-wired so as to facilitate a programmed interconnection to each logic input of adjacent cells, near-adjacent cells, and far cells, and the aforementioned cascade connection to adjacent upper and lower cells. This configuration allows adjacent and near-adjacent cells to be easily interconnected to form macro cells that conform to higher level functional blocks. The gate array in a preferred embodiment does not contain explicit routing channels; routing is effected using the prewired routing that is integral with each gate array cell.